1. Field of the Invention
The present invention relates to a decoding method and apparatus suitable for maximum likelihood decoding of a convolutional code, and more particularly, to a decoding method and apparatus suitably usable in a satellite broadcasting, etc.
2. Description of the Related Art
Recently, researches have been made to minimize the symbol error probability by soft-output of decoded code of concatenated codes and iterative output in the iterative decoding method and decoding methods suitable for acquisition of a soft-output are sought with a great interest. The soft output Viterbi algorithm disclosed in xe2x80x9cA Viterbi Algorithm with Soft-Decision Outputs and Its Application, Hagenauer and Hoeher, Proc. IEEE Global Telecoim. Conf GLOBECOM, pp. 47.1.1-47.1.7, November 1989xe2x80x9d is one of the decoding methods for soft output during decoding of an convolutional code. In the Viterbi algorithm with soft-decision outputs, each symbol is not output as a result of decoding but a likelihood of each symbol is output. Such an output is called a soft-output. What the soft-output Viterbi algorithm (will be referred to as xe2x80x9cSOVAxe2x80x9d hereinafter) is will be described.
As shown in FIG. 1, digital information is convolved by a convolutional encoder 101, an output from the convolutional encoder 101 is supplied to a decoder 103 via a memoryless channel 102 with noises, and the output is decoded by the decoder 103.
First, M states (transition) of a shift register in the convolutional encoder 101 are represented by m (0, 1, . . . , Mxe2x88x921), a state at a time t is represented by St, an input at the time t is represented by it, an output at the time t is represented by Xt, and an output sequence is represented by Xttxe2x80x2=Xt, Xt+1, . . . , Xtxe2x80x2.
The convolutional coding will start at a state SO=0 and end at a state ST=0 with output of X1T. The memoryless channel 102 with noises is supplied with X1T, and outputs Y1T. It is assumed here that Yttxe2x80x2 Yt, Yt+1, . . . , Ytxe2x80x2. The transition probability of the memoryless channel 102 with noises is defined by R(xc2x7|xc2x7) which will be as given by the expression (1) for all t (1xe2x89xa6txe2x89xa6T).                               Pr          ⁢                      {                                          Y                1                t                            ❘                              X                1                t                                      }                          =                              ∏                          j              =              1                        t                    ⁢                      xe2x80x83                    ⁢                      R            ⁡                          (                                                Y                  j                                ❘                                  X                  j                                            )                                                          (        1        )            
A likelihood of input information xcext is defined by the expression (2):                               λ          t                =                              Pr            ⁢                          {                                                i                  t                                =                                  1                  ❘                                      Y                    1                    T                                                              }                                            Pr            ⁢                          {                                                i                  t                                =                                  0                  ❘                                      Y                    1                    T                                                              }                                                          (        2        )            
The input information likelihood xcext is a one at the time t when Y1T has been received. It is a soft-output to be determined. Practically, however, the value of xcext itself is less frequently determined than its natural logarithmic value log xcext. In the following description, the log xcext will be referred to as xe2x80x9clogarithmic likelihood ratioxe2x80x9d.
With the SOVA, the likelihood is not directly determined but a likelihood of a path not selected at each time of the process of selection in the Viterbi decoding, in which a most likely path being sequence most likely to a received code sequence is derived, is used to determine a likelihood of a decoded bit of the most likely path, thereby determining the likelihood of each input information by approximation.
Assuming that the most likely path is PtML, the path not selected as a result of the comparison with the most likely path at a time j is Ptj, a bit entered at the time t of the path Pt is taken as I[Pt, t], the likelihood of the path Pt when Y1T is received is Pr(Pt|Y1T) and a set of the paths Ptj is xcfx81, a definition is made as given by the expression (3):
xcfx810(t)={Pr:Ptxcex5xcfx81, I[Pt, t|xe2x89xa0I[PtML, t]}xe2x80x83xe2x80x83(3)
With the SOVA, the logarithmic likelihood ratio of the decoded bit at the time t is computed by approximation using the expression (4). Thus, the logarithmic likelihood ration of the decoded bit can be determined as a path-metric difference during Viterbi decoding.                               log                                    max              ⁢                              {                                                      Pr                    ⁢                                          {                                              Pt                        ❘                                                  Y                          1                          T                                                                    }                                                        :                                      Pt                    ∈                                                                  ρ                        0                                            ⁡                                              (                        t                        )                                                                                            }                                                    Pr              ⁢                              {                                                      Pt                    ML                                    ⁢                                      Y                    1                    T                                                  }                                                    =                  log          ⁢                      {                                          max                ⁢                                  {                                                            Pr                      ⁢                                              {                                                  Pt                          ❘                                                      Y                            1                            T                                                                          }                                                              :                                          Pt                      ∈                                                                        ρ                          0                                                ⁡                                                  (                          t                          )                                                                                                      }                                            -                              logPr                ⁢                                  {                                                            Pt                      ML                                        ❘                                          Y                      1                      T                                                        }                                                                                        (        4        )            
Note that with the SOVA, the logarithmic likelihood ratio is computed as a likelihood of the most likely path in relation to the decoded bit, namely, in the form of the expression (5) or (6):
Decoded bit=0
xe2x86x92Pr{it=1|Y1T}/Pr{it=0|Y1T}(=xcext)xe2x80x83xe2x80x83(5)
Decoded bit=1
xe2x86x92Pr{it=0|Y1T}/Pr{1|Y1T}(=1/xcext)xe2x80x83xe2x80x83(6)
The SOVA algorithm will further be described below:
FIG. 2 shows the merging of paths in the state k at the time j. As shown, a path selected is represented by P1(k, j), and a path not selected is by P2(k, j). A state through which the path P1(k, j) passes at a time jxe2x88x921 is represented by s1(k), a state through which the path P2(k, j) passes is represented by s2(k), and a path-metric difference between the paths P1(k, j) and P2(k, j) is represented by xcex94k(j). Bits decoded between the paths P1(k, j) and P2(k, j) at the time t are represented by I[P1(k, j), t] and I[P2(k, j), t], respectively, and the logarithmic likelihood ratio between the decoded bits of survivor paths in the state k when paths counted up to the time t have been selected is represented by L{circumflex over ( )}t(k, j).
Using the above notation, the decoding procedure with the SOVA will be as follows:
With the SOVA, all the times and states t and k are first initialized to have a logarithmic likelihood ration of L{circumflex over ( )}t(k, 0).
Next, with the SOVA, operations given by the expressions (7) and (8) are made on all the states k and times t (t=1 to j) during path selection at each time j:
I[P1(k, j), t]xe2x89xa0I[P2(k, j), t]xe2x86x92L{circumflex over ( )}t(k, j)=min {L{circumflex over ( )}t(s1(k), jxe2x88x921), xcex94k(j)}xe2x80x83xe2x80x83(7)
I[P1(k, j), t]=I[P2(k, j), t]xe2x86x92L{circumflex over ( )}t(k, j)=min {L{circumflex over ( )}t(s1(k), jxe2x88x921)xe2x80x83xe2x80x83(8)
With the SOVA, assuming that the last time is T and the most likely state is k0, the logarithmic likelihood ratio being a last soft-output is determined as L{circumflex over ( )}t(k0, T).
When the SOVA is installed in a hardware, the hardware will be a SOVA decoder 110 architected as shown in FIG. 3.
The SOVA decoder 110 includes a branch-metric computation circuit 111 to compute a branch-metric which is a Hamming distance between a received signal and path, an add compare select (ACS) circuit 112 to compare the branch-metric computed by the branch-metric circuit 111 with a state-metric being a cumulative sum of the preceding branch-metrics, a nonnalization circuit 113 to normalize a new state-metric signal s113 output from the ACS circuit 112, a state-metric memory circuit 114 to store a normalized state-metric signal s114 output from the normalization circuit 113, and a path memory and likelihood update circuit 115 supplied with path selection information s116, metric-difference information s117 and a most likely state signal s118 from the ACS circuit 112 to output a decoded data s119 and logarithmic likelihood ratio s120.
When the SOVA decoder 110 is supplied with a received value Yt, a priory probability information log Pr(it=0) and log Pr(it=1) as s111, it will output the decoded data s119 being a result of decoding and the logarithmic likelihood ratio s120, respectively.
When the branch-metric computation circuit 111 is supplied with a received value and a priory probability information s111, it computes a branch-metric of the received data, and outputs the result of computation as branch-metric signal s112 to the downstream ACS circuit 112.
Based on the branch-metric signal s112 supplied from the branch-metric computation circuit 111 and state-metric signal s115 supplied from the state-metric memory circuit 114, the ACS circuit 112 adds the branch-metric and state-metric to each of two paths merging in a state for comparison of the two paths. Based on the result of comparison, the ACS circuit 112 selects a more likely path and takes it as a new state-metric. The ACS circuit 112 outputs the selected path as path selection information s116 to the downstream path memory and likelihood update circuit 115. Further the ACS circuit 112 outputs a metric difference found when a path is selected in each state as a metric difference s117 to the path memory and likelihood update circuit 115. Moreover, the ACS circuit 112 outputs a number of a having a minimum state-metric as most likely state signal s118 to the path memory and likelihood update circuit 115 and a newly obtained state-metric as new state-metric signal s113 to the downstream nonnalization circuit 113.
The path selection by the ACS circuit 112 will be explained concerning a convolutional encoder with a constraint length of 3 shown in FIG. 4. The convolutional encoder 130 corresponds to the convolutional encoder 51 shown in FIG. 1. The convolutional encoder 130 includes three adders 131a, 131b and 131c and two registers 132a and 132b. In the transition diagram (will be referred to as xe2x80x9ctrellisxe2x80x9d hereinafter) of this convolutional encoder 130, there are always two merging paths in each state at each time slot as shown in FIG. 5. As mentioned above, the ACS circuit 112 will add a branch-metric and state-metric between a received signal and path to each of the two paths merging in a state and compare the paths for comparison with the paths. Based on the result of comparison, the ACS circuit 112 will select a more likely one of the paths.
The normalization circuit 113 subtracts a minimum state-metric, for example, from the new state-metric signal s113 output from the ACS circuit 112 to nonnalize the new state-metric signal s113 to a value within a preset range, and outputs it as normalized state-metric signal s114 to the downstream state-metric memory circuit 114.
The state-metric memory circuit 114 stores the normalized state-metric signal s114 supplied from the nonnalization circuit 113, and feeds it as state-metric signal s115 back to the ACS circuit 112.
Based on the path selection information s116 output from the ACS circuit 112, the path memory and likelihood update circuit 115 stores the decoded bits on the survivor paths in each state, and updates the likelihood of each decoded bit using the metric difference information s117 output from the ACS circuit 112. Also, based on the most likely state signal s118 output from the ACS circuit 112, the path memory and likelihood update circuit 115 outputs information a constant length called xe2x80x9cterminating lengthxe2x80x9d before the information corresponding to the most likely path as decoded data s119, and likelihood information as logarithmic likelihood ratio s120.
The SOVA decoder 110 is architected quite identically to the conventional Viterbi decoder 140 which implements the Viterbi algorithm as shown in FIG. 6 except for the path memory and likelihood update circuit 115. That is, similarly to the SOVA decoder 110, the conventional Viterbi decoder 140 includes a branch-metric computation circuit 141 to compute a branch-metric, an ACS circuit 142 to add a branch-metric and state-metric to paths for comparison of the paths, a nonnalization circuit 143 to normalize a new state-metric signal s143 output from the ACS circuit 142, a state-metric memory circuit 144 to store a nonnalized state-metric signal s144 output from the normalization circuit 143, and a path memory circuit 145 supplied with path selection information s146 and metric-difference information s147 from the ACS circuit 142 to output decoded data s148.
As in the above, different from the conventional Viterbi decoder 140, the SOVA decoder 110 includes the path memory and likelihood update circuit 115 to output likelihood information.
The path memory and likelihood update circuit 115 will be described below with reference to FIGS. 7 to 9. As shown, in the path memory and likelihood update circuit 115, a memory cell MSB consisting of a selector and register is disposed on the trellis to shift, based on the path selection information s116 output from the ACS circuit 112, the content of the register when storing the decoded bit and that of the register when storing the likelihood information.
The memory cell MSB to store the decoded bit is architected as shown in FIG. 7. As shown, the memory cell MSB includes a selector 151 supplied with a select signal based on the path selection information s116 output from the ACS circuit 112 to select one of two input bits based on the select signal, and a register 152 to store as decoded bits the input bits selected by the selector 151. Note that the memory cell MSB to store the decoded bit is architected quite identically to the memory cell in the conventional Viterbi decoder 140 shown in FIG. 6.
On the other hand, the memory cell MSB to store the likelihood information is architected as shown in FIG. 8. That is, the memory cell MSB includes a selector 153 supplied with a select signal based on the path selection information s116 output from the ACS circuit 112 to select one of two likelihood information based on the select signal, a decision circuit 154 to judge whether two decoded bits b1 and b2 supplied from the memory cell MSB to store the decoded bit are in a relation that b1xe2x89xa0b2 and whether two metric differences xcex941 and xcex942 based on the metric difference information s117 output from the ACS circuit 112 are in a relation that xcex941 less than xcex942, a selector 155 to select the metric difference xcex941 when the result of decision from the decision circuit 154 is that b1xe2x89xa0b2 and xcex941 less than xcex942, and the metric difference xcex942 in other cases, and a register 156 to store as likelihood information the metric difference selected by the selector 155.
The memory cell MSB to store a decoded bit and memory cell MSP to store likelihood information are disposed as shown in FIG. 9 when the constraint length is 3. Note that these memory cells MSB and MSP are disposed correspondingly to the trellis of the convolutional encoder 130 shown in FIG. 5. In the SOVA decoder 110, the memory cell MSB to store a decoded bit and memory cell MSP to store likelihood information thus disposed save information on the survivor paths in each state in the registers, respectively. Each of the memory cells MSB and MSP is disposed in number for the terminating length. The SOVA decoder 110 will selection information corresponding to the most likely path and a decoded data and logarithmic likelihood ratio by selecting a most likely state output from the outputs of the last ones of the memory cells MSB and MSP, respectively. As will be evident, the memory cell MSB to store a decoded bit is architected quite identically to the path memory circuit 145 in the conventional Viterbi decoder 140 in FIG. 6.
The SOVA decoder 110 can implement the SOVA by an actual hardware.
The SOVA decoder 110 needs a number of memory cells MSB and a number of memory cells MSP for a number of states by the terminating length, respectively, as shown in FIG. 9. However, since in the SOVA decoder 110, the circuit scale of the memory cell MSP shown in FIG. 8 is larger than that of the memory cell MSB shown in FIG. 7, if the number of states and terminating length are larger, there will occur a problem that the circuit scale of the SOVA decoder 110 is considerably large in comparison with the conventional Viterbi decoder 140 shown in FIG. 6. To solve this problem, Joeressen and Berrou proposed the same approach independently of each other by their respective articles xe2x80x9cJoeressen, Vaupel and Meyxe2x80x94High-Speed VLSI Architectures for Soft-Output Viterbi Decoding, in Proc. Int. Conf. Applicat. Specific Array Processors. Oakland, Calif.: IEEE Computer Society Press. August 1992, pp. 373-384xe2x80x9d and xe2x80x9cBerrou, Adde, Angui and Faudeilxe2x80x94A Low Complexity Soft-Output Viterbi Decoder Architecture, in Proc. IEEE Int. Conf. Commune., Geneva, Switzerland, May 1993, pp. 737-740xe2x80x9d. This approach will be called xe2x80x9ctwo-step SOVAxe2x80x9d as they call in their articles, and described below.
With the two-step SOVA, after a Viterbi decoding for an terminating length is done once, the likelihood information is updated only for a selected path. The two-step SOVA will need a two-times larger number of memory cells to store the decoded bit than in the SOVA decoder 110 but a number of memory cells to store the likelihood information only for the terminating length. Therefore, the two-step SOVA permits to reduce the number of the memory cells to store the likelihood information. As the result, the two-step SOVA makes it possible to considerably reduce the scale of the path memory and likelihood update circuit as a whole in view of the circuit scale of the memory cell to store the likelihood information.
FIG. 10 shows a two-step SOVA decoder. The two-step SOVA decoder is generally indicated with a reference 160. As shown, the two-step SOVA decoder 160 includes a branch-metric computation circuit 161 to compute a branch-metric, an ACS circuit 162 to the branch-metric and state-metric to each of two paths merging in a state for comparison of the two paths, a nonnalization circuit 163 to normalize a new state-metric signal s163 output from the ACS circuit 162, a state-metric memory circuit 164 to store a nonnalized state-metric signal s164 output from the nonnalization circuit 163, an upstream path memory circuit 165 to store decoded bits on survivor paths in each state and output delay state information s169, a path selection information delay circuit 166 to delay path delay information s166, a metric difference delay circuit 167 to delay metric difference information s167, a selection circuit 168 to select from a metric difference delay signal s171 a signal indicative of a state corresponding to the delay state information s169, a downstream path memory circuit 169 to store decoded bits on survivor paths in each state and output most likely and merging path input information s173 and decoded bit s174, and a likelihood update circuit 170 to update the likelihood of the decoded bit and output a logarithmic likelihood ratio s175. Supplied with a received value Yt and a priory probability information log Pr(it=0) and log Pr(it=1) as s161, the two-step SOVA decoder 160 outputs the decoded data s174 and logarithmic likelihood ratio s175. It should be reminded here that the terminating length of the upstream path memory circuit 165 is indicated with D and that of the downstream path memory circuit 169 is with U.
Supplied with the received value and a priory probability information s161, the branch-metric computation circuit 161 computes a branch-metric of the received data and outputs the result of the computation as branch-metric signal s162 to the ACS circuit 162.
Based on the branch-metric signal s162 supplied from the branch-metric computation circuit 161 and state-metric signal s165 supplied from the state-metric memory circuit 164, the ACS circuit 162 adds a branch-metric and state-metric to each of two paths merging into a state for comparison of the paths, selects a more likely one of the paths based on the result of the comparison and takes it as a new state-metric. The ACS circuit 162 outputs the selected path as path selection information s166 to the upstream path memory circuit 165 and path selection information delay circuit 166. Also, the ACS circuit 162 outputs a metric difference found when a path is selected in each state as metric difference information s167 to the metric difference delay circuit 167. Further, the ACS circuit 162 outputs a number for a state having a minimum state-metric as most likely state signal s168 to the upstream path memory circuit 165 and the newly obtained state-metric as new state-metric signal s163 to the nonnalization circuit 163.
The nonnalization circuit 163 subtracts a minimum state-metric, for example, from the new state-metric signal s163 output from the ACS circuit 162 to nonnalize the new state-metric signal s163 to a value within a preset range, and outputs it as normalized state-metric signal s164 to the state-metric memory circuit 164.
The state-metric memory circuit 164 stores the normalized state-metric signal s164 supplied from the nonnalization circuit 163 and feeds it as state-metric signal s165 back to the ACS circuit 162
Based on the path selection information s166 output from the ACS circuit 162, the upstream path memory circuit 165 stores decoded bits on survivor paths in each state, and outputs, based on the most likely state signal s168 output from the ACS circuit 162, numbers of the states counted back over the terminating length D from the most likely path as delay state information s169 to the selection circuit 168 and downstream path memory circuit 169.
The path selection information delay circuit 166 is provided to delay the path selection information s166 output from the ACS circuit 162 by the terminating length D of the upstream path memory circuit 165 and output it as path selection information delay signal s170 to the downstream path memory circuit 169.
The metric difference delay circuit 167 delays the metric difference information s167 output from the ACS circuit 162 by the terminating length D of the upstream path memory circuit 165, and outputs it as metric difference delay signal s171 to the selection circuit 168.
Based on the delay state information s169 supplied from the upstream path memory circuit 165 and metric difference delay signal s171 supplied from the metric difference delay circuit 167, the selection circuit 168 selects a signal indicative of a state corresponding to the delay state information s169 from the metric difference delay signal s171, and outputs it as metric difference delay select signal s172 to the likelihood update circuit 170.
Based on the path selection information delay signal s170 supplied from the path selection information delay circuit 166, the downstream path memory circuit 169 stores decoded bits on survivor paths in each state. Also, based on the delay state information s169 output from the upstream path memory circuit 165, the downstream path memory circuit 169 outputs, as decoded bit s174, information further counted back over an terminating length U from the most likely path. Based on the delay state information s169, the downstream path memory circuit 169 outputs input information corresponding to the most likely path and input information corresponding to paths merging into the most likely path, only for the terminating length, respectively, as most likely and merging path input information s173 to the likelihood update circuit 170.
The likelihood update circuit 170 updates input information corresponding to the most likely path, that is, the likelihood of the decoded bit, based on the metric difference delay select signal s172 supplied from the selection circuit 168 and the most likely and merging path input information s173 supplied from the downstream path memory circuit 169, and outputs, as a logarithmic likelihood ratio s175, likelihood information the terminating length U before the downstream path memory circuit 169.
As in the above, the blocks of the two-step SOVA decoder 160, including the branch-metric computation circuit 161 to the upstream path memory circuit 165, are architected quite identically to those in the conventional Viterbi decoder 140 having previously been described with reference to FIG. 6.
The downstream path memory circuit 169 and likelihood update circuit 170 will be described below with reference to FIGS. 11 to 13. In the downstream path memory circuit 169, memory cells MSB to store decoded bits, shown in FIG. 7, are disposed similarly to those in the conventional Viterbi decoder 140 to shift information bits corresponding to survivor paths in each state based on the path selection information delay signal s170, and information bits are supplied from all the memory cells MSB to store the decoded bits to a selection circuit (not shown), thus providing input information corresponding to the most likely path and input bits corresponding to paths merging in the most likely path as most likely and merging path input information s173 to the likelihood update circuit 170 based on the delay state information s169 output from the upstream path memory circuit 165. When the constraint length is 3, the memory cells MSB provided in the downstream path memory circuit 169 to store the decoded bits and selection circuit are disposed as shown in FIG. 11.
On the other hand, the likelihood update circuit 170 include memory cells MSP to store the likelihood information, architected as shown in FIG. 12. That is, each of the memory cell MSP includes a decision circuit 171 supplied with most likely path input information b1 and merging path input information b2, based on the most likely and merging path input information s173 supplied from the downstream path memory circuit 169, and also with a metric difference xcex941 based on the metric difference delay select signal s172 supplied from the selection circuit 168 and likelihood information xcex942 supplied from the memory cell MSP to store the preceding likelihood information, to judge whether the most likely input information b1 and merging path input information b2 are in a relation that b1xe2x89xa0b2 and whether the metric difference xcex941 and likelihood information xcex942 are in a relation that xcex941 less than xcex942, a selector 172 to select the metric difference xcex941 when the decision circuit 171 has decided that b1xe2x89xa0b2 and xcex941 less than xcex942, and the likelihood information xcex942 in other cases, and a register 173 to store the metric difference or likelihood information selected by the selector 172.
In the likelihood update circuit 170, the memory cells MSP to store the likelihood information are disposed in an array as shown in FIG. 13, to update only the likelihood for an input bit corresponding to the most likely path determined by the upstream path memory circuit 165 for the terminating length U of the downstream path memory circuit 169, and output the likelihood information being a result of the updating as a logarithmic likelihood ratio.
The two-step SOVA decoder 160 is adapted to determine a to-be-decoded most likely path by tracing back paths for a sufficiently long time, that is, an terminating length D, from a most likely state at a time t as shown in FIG. 14. With the metric difference and path selection information having been delayed, the two-step SOVA decoder 160 will be able to update the likelihood of only the most likely path through comparison between paths merging in the most likely path and the most likely path at a time t-D.
Since a smaller terminating length U of the downstream path memory circuit 169 than the terminating length D of the upstream path memory circuit 165 will do as disclosed in xe2x80x9cBerrou, Adde, Angui and Faudeilxe2x80x94A Low Complexity Soft-Output Viterbi Decoder Architecture, in Proc. IEEE Int. Conf Coimmun., Geneva, Switzerland, May 1993, pp. 737-740xe2x80x9d, the two-step SOVA decoder 160 can be embodied at a circuit scale for the same code, approximately double that of the conventional Viterbi decoder 140 shown in FIG. 6 even if the delay memory is included.
The conventional Viterbi decoder 140 has the path memory circuits thereof formed from register arrays as in the SOVA decoder 110, for example (this will be referred to as xe2x80x9cregister shift methodxe2x80x9d hereinafter). Recently, however, a method of decoding by storing path selection information in a RAM (random-access memory) and tracing the information (will be referred to as xe2x80x9ctrace-back methodxe2x80x9d hereinafter) has been researched. The trace-back method will be discussed herebelow:
For operation of the Viterbi decoder at a high speed, only one access is possible to the RAM at every clock. The operation of the path memory circuit to decode by one access to each RAM will be described concerning the use of four single-port memories as disclosed in xe2x80x9cEdwardsxe2x80x94A 45-Mbits/sec. VLSI Viterbi Decoder for Digital Video Applications, IEEE NatI. Telesystems Conf Vol. 1993, pp. 127-130xe2x80x9d.
First, there are provided four single-port RAMs each having a number of bits for a number of states and a number of words for an terminating length. Path selection information for the number of states is supplied at every clock from the ACS circuit to the path memory circuit. As shown in FIG. 15, the four RAMs have the following functions thereof switched from one to another at every clock for the terminating length.
The function of the first RAM is to write path selection information as shown in FIG. 15, that of the second RAM is to trace based on the written path selection information without decoding as shown in FIG. 15B, that of the third RAM is to wait without access as shown in FIG. 15C, and that of the fourth RAM is to trace based on the result of tracing and output decoded bits as shown in FIG. 15D. That is, the four RAMs have their respective functions switched from one to another at every clock for the terminating length.
With these functions of the RAMs, the Viterbi decoder can provide a high-speed decoding. Since decoded bits determined by tracing based on the result of tracing are in a sequence opposite to the original time series of them, however, in the Viterbi decoder, the sequence of the decoded bits is corrected with the Last-in First-out (LIFO) operation to the original one before they are output.
In the Viterbi decoder using the aforementioned trace-back method, the circuit scale can be considerably reduced in comparison with that when the register-shift method is adopted in the Viterbi decoder since the RAMs will need a considerably smaller area than that the registers need when the code constraint length and decoding terminating length are increased.
However, the downstream path memory circuit of the two-step SOVA decoder has to read all input information bits for the terminating length at the same time while each of the RAMs operating at a high speed can be accessed only once per clock. Therefore, it is difficult to form the path memory circuit of the two-step SOVA decoder from RAMs.
Since the conventional two-step SOVA decoder adopts the register-shift method, the circuit scale will be very large when the code constraint length and decoding terminating length are increased, so long as the register array is used to form the path memory circuit.
It is therefore an object of the present invention to overcome the above-mentioned drawbacks of the prior art by providing a decoding method and apparatus to implement a SOVA decoder whose circuit scale is small and can operate at a high speed even when the code constraint length and decoding terminating length are large.
The above object can be attained by providing, according to the present invention, a decoding method of decoding, in the soft-output Viterbi manner, an input convolutional code to provide a decoded data and likelihood information, including steps of:
storing, into a random-accessible path selection information storing means, path selection information indicative of more likely paths selected at each transition of the convolutional code;
storing, based on a trace result signal indicative of a result of a tracing effected for a terminating length based on the path selection information, a result of tracing of a most likely path being a sequence most likely to that of the convolutional code into a trace result storing means;
selecting, based on a delayed trace result signal indicative of a result of tracing of the most likely path stored in the trace result storing means and thus delayed, a metric difference for the most likely path from a metric difference delay signal resulted from a delay of the metric difference when the more likely paths are selected at each transition of the convolutional code, and storing it into a metric difference storing means;
storing, based on the delayed trace result signal and a delayed most likely metric difference signal indicative of a metric difference for the most likely path stored in the metric difference storing means, a minimum value of the metric difference for the most likely path into a minimum value storing means at each transition of the convolutional code; and
acquiring the likelihood information based on the minimum value.
Since the minimum value of the metric difference is stored into the minimum value storing means at each transition of the convolutional code, the above decoding method according to the present invention makes it unnecessary to read all input convolutional codes for the terminating length at the same time for acquisition of the likelihood information, and enables to store the path selection information into the random-accessible path selection information storing means. Therefore, the decoding method according to the present invention implements the trace-back method in which the path selection information stored in the random-accessible path selection information storing means is traced. Thus, even if the code constraint length and decoding terminating length are larger than in the conventional register-shift method, the decoding can be done at a high speed and with a small circuit scale.
Also the above object can be attained by providing, according to the present invention, a decoder for decoding, in the soft-output Viterbi manner, an input convolutional code to provide a decoded data and likelihood information, including:
means for storing, into a random-accessible path selection information storing means, path selection information indicative of more likely paths selected at each transition of the convolutional code;
means for storing, based on a trace result signal indicative of a result of a tracing effected for an terminating length based on the path selection information, a result of tracing of a most likely path being a sequence most likely to that of the convolutional code into a trace result storing means;
means for selecting, based on a delayed trace result signal indicative of a result of tracing of the most likely path stored in the trace result storing means and thus delayed, a metric difference for the most likely path from a metric difference delay signal resulted from a delay of the metric difference when the more likely paths are selected at each transition of the convolutional code, and storing it into a metric difference storing means; and
means for storing, based on the delayed trace result signal and a delayed most likely metric difference signal indicative of a metric difference for the most likely path stored in the metric difference storing means, a minimum value of the metric difference for the most likely path into a minimum value storing means at each transition of the convolutional code; and
the likelihood information being acquired based on the minimum value.
Since the minimum value of the metric difference is stored into the minimum value storing means at each transition of the convolutional code, the above decoder according to the present invention has not to read all input convolutional codes for the terminating length at the same time for acquisition of the likelihood information, and can store the path selection information into the random-accessible path selection information storing means. Therefore, the decoding method according to the present invention implements the trace-back method in which the path selection information stored in the random-accessible path selection information storing means is traced. Thus, even if the code constraint length and decoding-terminating length are larger than in the conventional register-shift method, the decoder can have a small circuit scale and provide a high-speed decoding.